#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

string ip; 

bool isIp(string &cur)
{
    stringstream ss(cur);
    string str;
    ip.clear();
    while(ss >> str) {
         if (str.size() > 1 && str[0] == '0') return false;
         int i = atoi(str.c_str());
         if (i > 255) return false;
        ip += str;
        ip += '.';    
    }   
    ip = ip.substr(0, ip.size()-1);
    return true;
}

void dfs(string &s, int index, int count, string &cur, vector<string> &ans)
{
    if (count == 4 && index == s.size()) {
        if (isIp(cur)) {
         //   cout << cur << endl;
            ans.push_back(ip);
        }   
        return;
    }   
    if (count == 4 || index == s.size()) 
        return;    

    for (int i = 1; i <= 3  && index + i <= s.size(); i++) {
        string str = cur + " " + s.substr(index, i); 
        dfs(s, index+ i, count+1, str , ans);
    }   

}



class Solution {
public:

vector<string> restoreIpAddresses(string s)
{
    vector<string> ans;
    if (s.size() < 4) return ans;
    string cur;
    int count = 0;
    dfs(s, 0, count, cur, ans);
    return ans;
}
};

int main(int argc, char **argv)
{
    Solution mySolu;
    vector<string> ans = mySolu.restoreIpAddresses("25525511135");
    for (int i = 0; i < ans.size(); i++)
	cout << ans[i] << endl;




}
